package Leetcode.每日一题;

import java.util.Arrays;

/**
 * @Author: kirito
 * @Date: 2024/5/4 11:49
 * @Description:
 * 规划兼职工作
 * 困难
 * 相关标签
 * 相关企业
 * 提示
 * 你打算利用空闲时间来做兼职工作赚些零花钱。
 *
 * 这里有 n 份兼职工作，每份工作预计从 startTime[i] 开始到 endTime[i] 结束，报酬为 profit[i]。
 *
 * 给你一份兼职工作表，包含开始时间 startTime，结束时间 endTime 和预计报酬 profit 三个数组，请你计算并返回可以获得的最大报酬。
 *
 * 注意，时间上出现重叠的 2 份工作不能同时进行。
 *
 * 如果你选择的工作在时间 X 结束，那么你可以立刻进行在时间 X 开始的下一份工作。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
 * 输出：120
 * 解释：
 * 我们选出第 1 份和第 4 份工作，
 * 时间范围是 [1-3]+[3-6]，共获得报酬 120 = 50 + 70。
 * 示例 2：
 *
 *
 *
 * 输入：startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
 * 输出：150
 * 解释：
 * 我们选择第 1，4，5 份工作。
 * 共获得报酬 150 = 20 + 70 + 60。
 * 示例 3：
 *
 *
 *
 * 输入：startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
 * 输出：6
 *
 *
 * 提示：
 *
 * 1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
 * 1 <= startTime[i] < endTime[i] <= 10^9
 * 1 <= profit[i] <= 10^4
 */

public class jobScheduling {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 3};
        int[] b = {3, 4, 5, 6};
        int[] c = {50, 10, 40, 70};
        System.out.println(new jobScheduling().jobScheduling(a, b, c));
    }
    //https://leetcode.cn/problems/maximum-profit-in-job-scheduling/solutions/1913089/dong-tai-gui-hua-er-fen-cha-zhao-you-hua-zkcg/?envType=daily-question&envId=2024-05-04
    // 定义一个方法来解决工作调度问题，该方法接受工作的开始时间、结束时间和利润数组
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length; // 获取工作的数量
        int[][] jobs = new int[n][]; // 创建一个二维数组来存储工作的开始时间、结束时间和利润
        // 填充jobs数组
        for (int i = 0; i < n; i++) {
            jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
        }
        // 根据工作的结束时间对jobs进行排序
        Arrays.sort(jobs, (a, b) -> a[1] - b[1]);
        int[] dp = new int[n + 1]; // 动态规划数组，dp[i]表示第i个工作能获得的最大利润
        // 遍历所有工作，除了最后一个，因为最后一个工作可以直接加上最大利润
        for (int i = 1; i <= n; i++) {
            // binarySearch方法用于找到可以和当前工作兼容的最早结束时间
            int k = binarySearch(jobs, i - 1, jobs[i - 1][0]);
            System.out.println(i+"  "+k);
            // dp[i]表示第i个工作能带来的最大利润，等于不选择第i个工作的最大利润或者选择第i个工作并加上之前最大利润
            dp[i] = Math.max(dp[i - 1], dp[k] + jobs[i - 1][2]);
        }
        // 返回最后一个工作的最大利润，即整体的最大利润
        return dp[n];
    }

    // 定义二分搜索方法，用于找到在jobs数组中第一个结束时间大于或等于target的元素的索引
    public int binarySearch(int[][] jobs, int right, int target) {
        int left = 0; // 设置左边界
        while (left < right) { // 进行二分搜索
            int mid = left + (right - left) / 2; // 计算中间索引
            if (jobs[mid][1] > target) { // 如果中间元素结束时间大于target
                right = mid; // 移动右边界到中间索引
            } else { // 如果小于或等于target
                left = mid + 1; // 移动左边界到中间索引之后
            }
        }
        return left; // 返回左边界，即第一个结束时间大于或等于target的元素的索引
    }

}